package leetcode.dichotomy.democ;

import sun.java2d.pipe.hw.AccelDeviceEventListener;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author cyt
 * @create 2020-09-21 19:48
 */
public class Tc {
    public static void main(String[] args) {
        Tc tc = new Tc();
        int[] ints = {1, 2, 3, 4, 5};
        List<Integer> integers = tc.findClosestElements(ints, 4, -1);
        integers.forEach(System.out::println);
    }

    /**
     * 输入: [1,2,3,4,5], k=4, x=3
     * 输出: [1,2,3,4]
     * <p>
     * 给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
     * 如果有两个数与 x 的差值一样，优先选择数值较小的那个数。
     */
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List list = Arrays.asList(arr);
        List ans = new ArrayList<>();
        int length = arr.length;
        int right = length;
        int left = 0;
        int index = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == x) {
                index = mid;
                break;
            } else if (arr[mid] < x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (index != 0) {
            int q = index;
            while (q >= 0) {
                ans.add(arr[q--]);
            }
            for (int j = index + 1; j < k; j++) {
                ans.add(arr[j]);
            }
        } else {
            ans = Arrays.stream(arr).boxed().collect(Collectors.toList()).subList(0, k);
        }
        Collections.sort(ans);
        return ans;
    }
}
